/**
 * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点
 * 
 * 链表长度在[0, 20000]范围内。 链表元素在[0, 20000]范围内
 * 
 * 进阶：如果不得使用临时缓冲区，该怎么解决？
 * 
 * 
 * 解决思路：
 * 1. 利用标记数组存储出现过的数值(不是存储对应的元素值而是索引标记， 存储元素的话还需要遍历比较)
 * 2. 利用双指针，指针 cur 指向当前节点， 指针 p 用于遍历
 * 
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
#include "common.h"


// struct ListNode* removeDuplicateNodes(struct ListNode* head){
//     if (head == NULL || head->next == NULL)
//         return NULL;
//     struct ListNode* current = head;
//     struct ListNode* p = current;
//     while(current){
//         p = current;
//         while(p->next){
//             if (current->val == p->next->val){
//                 p->next = p->next->next;
//             }
//             else
//                 p = p->next;
//         }
//         current = current->next;
//     }
//     return head;
// }

struct ListNode* removeDuplicateNodes(struct ListNode* head){
    //判断是否需要遍历
    if(head==NULL || head->next==NULL)  
        return head;

    //利用val的值在0~20000之间，标记是否出现过
    int index[20001] = {0}; 
    index[head->val] = 1;
    struct ListNode *pre = head, *q = head->next;
    while(q)
    {
        //当前val未出现过，保存当前val，修改pre和p指针
        if(index[q->val]==0)   
        {
            index[q->val] = 1;
            pre = q;
            q = q->next;
        }
        //当前值已经出现过了，删除当前节点
        else    
        {
            pre->next = q->next;
            q = pre->next;
        }
    }
    return head;
}
